# 42/100 二叉树-将有序数组转换为二叉搜索树 (也就是AVL树, 也叫平衡二叉树Balanced Binary Tree)
# leetcode第108题: https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/12
from leetcode.bds import TreeNode, TreeConverter
import leetcode.test as test


def sortedArrayToBST(nums: list[int]):
    """
    1, 2, 3, 4, 5, 6, 7, 8
             6
           /  \
          4    7
         / \    \
        2   5    8
       /\
      1  3
    """
    n = len(nums)
    if n < 2:
        return TreeNode(nums[0])

    def in_order(l: int, r: int):
        if l > r:
            return None
        mid = (l + r + 1) // 2

        root = TreeNode(nums[mid])
        root.left = in_order(l, mid - 1)
        root.right = in_order(mid + 1, r)
        return root

    return TreeConverter.tree_to_list(in_order(0, n - 1))


if __name__ == '__main__':
    inp = [{"nums": [-10, -3, 0, 5, 9]}, {"nums": [1, 3]}, ]
    out = [[0, -3, 9, -10, None, 5], [3, 1]]
    test.test_function(sortedArrayToBST, inp, out)
